perm filename GEOM2[3,BGB]1 blob
sn#115077 filedate 1974-08-11 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00009 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 {⊂C<NF3αGEOMED.λ30P38I100,0JUFA}
C00006 00003
C00012 00004
C00018 00005 <Homogeneous Coordinates>. The Euclidean routines involving
C00024 00006 <Metric Routines>. Given one or several geometric entities,
C00030 00007 ⊂3.4 Image Synthesis: Perspective Projection and Clipping.⊃
C00034 00008
C00037 00009 ⊂3.5 Image Analysis: Interface to CRE.⊃
C00039 ENDMK
C⊗;
{⊂C;<N;F3;αGEOMED.;λ30;P38;I100,0;JUFA}
⊂3.3 Euclidean Routines.⊃
The Euclidean routines of GEOMED fall roughly into four groups:
transformations, metrics, tram routines and space simulators. The
Euclidean transformations are translation, rotation, dilation and
reflection (following Klein's Erlangen Program, 1872); the Euclidean
metric routines compute distances, angles, areas, volumes and
inertia tensors; the tram routines create or alter tram nodes which
are the main topic of this sub section; the final group of routines
perform spatial simulations such as collision, intersection,
propinquity, occupancy and occultation.
<Tram Nodes>. A tram node contains twelve real numbers;
fundamental to all the Euclidean routines is the curious fact that
tram nodes have two interpretations: they may represent a coordinate
system or they may represent a Euclidean transformation. ~As a
coordinate system~, the twelve numbers contain a location of the
origin of the coordinate system as well as the three components of
each of the three unit vectors of the axes of the coordinate system.
~As a transformation~, the application of a tram node to a vertex is
defined by the procedure named SCREW, given below.{
λ10;T100,600,700,800,930;JA}
~Tram as a Coordinate System:~ {I∂0,540;} <Tram Node Data Field Names>
location of origin of coordinates: XWC, YWC, ZWC, LOCATION VECTOR.
components of X-axis unit vector: IX, IY, IZ,
components of Y-axis unit vector: JX, JY, JZ, ORIENTATION MATRIX.
components of Z-axis unit vector: KX, KY, KZ.{T-1;}
~Tram as a Transformation:~{W100;JAF3}
COMMENT APPLY TRAM Q TO VERTEX V POSTFIX;
PROCEDURE SCREW (INTEGER V,Q);
BEGIN REAL X,Y,Z;
X ← XWC(V); Y ← YWC(V); Z ← ZWC(V);
XWC(V) ← X*IX(Q) + Y*JX(Q) + Z*KX(Q) + XWC(Q);
YWC(V) ← X*IY(Q) + Y*JY(Q) + Z*KY(Q) + YWC(Q);
ZWC(V) ← X*IZ(Q) + Y*JZ(Q) + Z*KZ(Q) + ZWC(Q);
END;{λ30;W0;JUFA}
\Generalizing, the procedure APTRAM(ENTITY,TRAM) applies a tram to an
arbitrary entity. The APTRAM procedure is formed by surrounding the
SCREW procedure with suitable type checking and data structure
tracing mechanisms so that a tram can be applied (postfix) to almost
anything: bodies, faces, edges, vertices, as well as to other trams,
camera models and window nodes.{Q}
{I130,0;} To repeat for emphasis, a tram node has two interpretations;
a tram node may be interpreted as a coodinate system and the very
same tram node may be interpreted as a Euclidean transformation. Now
one source of confusion, is that a coordinate system tram is a
definition of one coordiate system (call it the body coordinates) in
term of another coordinate system (call it the world coordinates).
The application of a body coordinate system tram to an entity in body
coordinates brings the entity down into the world coordinate system
in which the tram is defined. To say it another way, the rule is that
APTRAM(BODY,TRAM) converts from body coordinates to world
coordinates, whereas APTRAM(BODY,INTRAM(TRAM)) converts world
coordinates to body coordinates. The procedure INTRAM inverts a tram
node in the manner given below. As alluded to in example #2, body
nodes carry a pointer to a tram defining a system of body coordinates
so that Euclidean transformtion can be relocated, that is performed
relative to convenient sets of axes and origins.{W250;λ10;JAF3}
INTEGER PROCEDURE INTRAN (INTEGER Q);
BEGIN "INTRAM"
REAL X,Y,Z;
X ← XWC(Q); Y ← YWC(Q); Z ← ZWC(Q);
XWC(Q) ← -(X*IX(Q) + Y*IY(Q) + Z*IZ(Q));
YWC(Q) ← -(X*JX(Q) + Y*JY(Q) + Z*JZ(Q));
ZWC(Q) ← -(X*KX(Q) + Y*KY(Q) + Z*KZ(Q));
IY(Q) ↔ JX(Q); IZ(Q) ↔ KX(Q); JZ(Q) ↔ KY(Q);
RETURN(Q);
END "INTRAM";{W0;λ15;JUFA}
{|;λ10;JAFA}
BOX 3.2 {JC} EUCLIDEAN TRANSFORMATIONS {I∂15,0;T150,300,350;}
ENTITY ← APTRAM(ENTITY,TRAM);
TRAM ← INTRAM(TRAM);
RESULT ← TRANSL(XWD(TRAM,ENTITY),DX,DY,DZ);
RESULT ← ROTATE(XWD(TRAM,ENTITY),WX,WY,WZ);
RESULT ← SHRINK(XWD(TRAM,ENTITY),SX,SY,SZ);
{|;T-1;λ30;JU;FA}
Pragmatically, the creation, relocation and application of a
tram node are invoked all at once by an appropriate Euclidean
transformation routine. The transformation routines are listed in box
3.2 with APTRAM and INTRAM. As a further pragmatic device, the
first argument of the Euclideans is "microcoded" using the XWD
notation which packs two links into one word. The expression
XWD(A,B) is equivalent to the expression (A*2↑18 + (B MOD 2↑18)),
where A and B are positive integers. When the entity of the first
argument of the Euclidean routines is zero, the transformations
create and return a tram node; when the entity of the first argument
is not zero, the transformation create a tram, apply it to the
entity, kill the tram node and return the entity. When the first
argument carries a tram as well as an entity (using the XWD notation)
the desired transformation (or creation) is done with respect to the
coordinate system defined in the given tram, (this is called
coordinate relocation). When the first argument is negative the body
coordiates tram is retrieved and used for relocation of the
transformation. Most bodies carry a tram pointer (in the link field
named TRAM) which defines body coordinates; the body coordinates of a
face, edge or vertex is taken as the TRAM of the BGET of the face,
edge or body; a zero TRAM link is mapped into a zero translation,
unit rotation matrix tram by all the Euclidean routines. Finally, the
actual transformation is specified by three giving components of a
vector; the meaning of a translation vector is obvious, rotation
vectors are explained in a subsequent paragraph and a scale vector is
a triple of factors which are multiplied into the components of all
the vertices of an entity with respect to the axes of transformation.
Reflections are specified as negative shrinks; a reflection
on one or three axes will evert a body's surface orientation.
There are numerous ways to create and alter a tram node; box
3.3 list further tram routines. The MKTRAM routine simply returns an
identity tram with zero translation and zero rotation (that is a unit
rotation matrix). The MKTRMA routine creates a tram from the Euler
angles pan, tilt and swing (developed in detail starting on page 107
of [Goldstein]). The Euler angles come conveniently close to the
rotation degrees of freedom of automatic camera mounts, but unlike a
rotation vector the Euler angles are undesirably discontinous at
zenith and nadir.{|;λ10;T200,700;JAFA}
BOX 3.3 {JC} TRAM ROUTINES {I∂15,0;}
TRAM ← MKTRAM; Returns an identity tram.
TRAM ← MKTRMA(PAN,TILT,SWING); Makes a tram from Euler angles.
TRAM ← MKTRMF(FACE); Makes a tram from a Face.
TRAM ← MKTRME(EDGE); Makes a tram from an Edge.
TRAM ← MKTRMV(WX,WY,WZ); Makes a tram from a rotation vector.
TRAM ← NORM(TRAM); Normalization to unit vectors.
TRAM ← ORTHO1(TRAM); Orthogonalize by worst case.
TRAM ← ORTHO2(TRAM); Orthogonalize by two cross products:
K ← (I CROSS J) and J ← (K CROSS I).
{|;λ30;T-1;JUFA}
<The Rotation Matrix>. The nine elements named IX, IY, IZ,
JX, JY, JZ, KX, KY and KZ form what is know as a three by three
rotation matrix. By virtue of the definition of rigid object
rotation, the tram rotation matrix must be maintained orthonormal.
(The trams created by SHRINK are tolerated as a special case which
are not considered to be rigid rotations). Orthonormality is maintain
with the aided of three routines: NORM(TRAM) which normalizes the
rows vectors of a tram rotation matrix; ORTHO1 which orgonalizes a
rotation matrix by comparing the sums of pairs of dot products of
pairs of the three unit vectors; the unit vector that is most out of
allignment is recomputed by crossing the other two (ORTHO1 performs
its check twice and then exits); and ORTHO2, which coerces
orthogonality by setting row vector K to the cross product of rows I
and J followed setting row vector J to the cross product of rows K
and I.
<The Rotation Vector>. All 3-D rotations can be expressed as
a vector where the direction of the vector specifies the axis of
rotation and where the magnitude of the vector specifies the amount
of rotation in radians. Given such a rotation vector WX, WY, WZ with
direction cosines CX, CY, CZ and magnitude W in radians; let CW be
cosine(W) and SW be sine(W) and define a function called SIGN which
returns positive or negative one depending on whether its argument is
positive or negative; then the relation between a rotation matrix and
a rotation vector can be listed:{λ10;T10,430,850;JA;FA}
~Rotation vector to Rotation matrix:~
IX = (1-CW)*CX*CX + CW IY = (1-CW)*CY*CX + CZ*SW IZ = (1-CW)*CZ*CX - CY*SW
JX = (1-CW)*CX*CY - CZ*SW JY = (1-CW)*CY*CY + CW JZ = (1-CW)*CZ*CY + CX*SW
KX = (1-CW)*CX*CZ + CY*SW KY = (1-CW)*CY*CZ - CX*SW KZ = (1-CW)*CZ*CZ + CW{
λ10;T40,100,150;}
~Rotation matrix to Rotation vector:~
WX = SIGN(JZ-KY)*ACOS(0.5*(IX+JY+KZ-1))*SQRT(+IX-JY-KZ)/(3-IX-JY-KZ));
WY = SIGN(KX-IZ)*ACOS(0.5*(IX+JY+KZ-1))*SQRT(-IX+JY-KZ)/(3-IX-JY-KZ));
WZ = SIGN(IY-JX)*ACOS(0.5*(IX+JY+KZ-1))*SQRT(-IX-JY+KZ)/(3-IX-JY-KZ));{
λ30;T-1;JUFA}
<Homogeneous Coordinates>. The Euclidean routines involving
trams could be written out in terms of the 4-D homogeneous
coordinates frequently found in computer graphics, by suffixing a
column to each tram and a fourth component to each vertex.{λ10;I∂-10,0;
T200,400,600,800,1000;JAFA}
1 XWC YWC ZWC
{I∂18,∂0;}TRAM4D ={I∂-18,∂0;} 0 IX IY IZ
0 JX JY JZ
0 KX KY KZ{λ30;T-1;JUFA}
\I did not use homogeneous coordinates in GEOMED for three reasons:
first, the computer at hand, (a PDP-10) has floating point arithmetic
hardware so that homogeneous components were not need for numerical
scaling; second, the homogeneous representation requires more
coordinates per vertex and more multiplications per transformation
than the GEOMED representation; and third, my intuition is stronger
in affine metric geometry than it is in homogeneous projective
geometry.
<Elements of Confusion, Convention and Craft.> There are
many of mathematical approachs to rotation, translation and
projection among which a computer geometer must distinguish: (i).
matrix vs. algebraic notation; (ii). postfix vs. prefix
transformation application; (iii). row vs. column vertices; (iv). 4-D
homogeneous vs. 3-D affine coordinates; (v). rotation vector vs.
Euler angles and so on. At the moment, I favor algebraic notation,
postfix transformations, row vertices, 3-D coordinates and rotation
specification by vector; there probably isn't any completely natural
or superior system of conventions.
In GEOMED, tram nodes were until recently called frame nodes,
however I wish to abandoned all use of the word <frame> for three
reasons: first, the term is ambiguous and over used (even within
graphics alone); second, the term does not include the notion of
transformation; and third, the term risks confusion (or association)
with the connotations of [Minsky] and [Winograd]. the connotation of
a <Frame System> as a modular mental universe of stereotyped world
situations. In geometric modeling, the word <frame> can be replaced
in all three of its usual graphics applications: the <frame of
reference> or <coordinate frame> is now a <coordinate system>, the
<frame> of a movie film is now an <image>, the <frame> of a display
screen is now a <window> or <border>.
<Metric Routines>. Given one or several geometric entities,
the Euclidean metric routines listed in box 3.5 compute length,
area, volume, angle or moments of inertia. The DISTANCE routine
computes the distance between two anythings in a reasonable manner;
the measure routine returns the volume, area or length of bodies,
faces or edges respectively (by a pragmatic argument hack, the
measure of a negative body is its surface area). The ANGLE routine
computes the angle between two entities by returning the arc cosine
of the normalize inner product of two vectors: vertices are
interpreted as vectors from the origin of the body in which they
belong, edge are vectors from their NVT to their PVT, faces are taken
as their normal vector and bodies are represented by the K unit
vector of their body coordinates tram; trams and cameras also are
mapped into K unit vectors.{|;λ10;JAFA}
BOX 3.5 {JC} METRIC ROUTINES {I∂15,0;T200,400,600;}
VALUE ← DISTANCE(ENTITY,ENTITY);
VALUE ← MEASURE(ENTITY);
RADIANS ← ANGLE(ENTITY,ENTITY);
RADIANS ← ANGL3V(V1,V2,V3);
RADIANS ← ANGLCW(EDGE);
RADIANS ← ANGLCCW(EDGE);
VALUE ← DETERM(TRAM);
NODE ← INERTIA(BODY);
{|;λ30;T-1;JUFA}
\Whereas the arc cosine function determines returns an angular value
between zero and pi; the routines ANGL3V, ANGLCW and ANGLCCW are
employ the arc tangent to return an angular value between negative pi
and positive pi. The ANGL3V return the angle between the vector
(V3-V2) and (V2-V1), the ANGLCW(E) returns the angle between E and
PCW(E), ANGLCW(-E) returns arctan of E and NCW, likewise ANGLCCW
returns values for E and PCCW or E and NCCW. The DETERM of a tram is
the determinate of the rotation matrix of a tram. Finally, the
INERTIA of a body is a sixtuplet: MXX, MYY, MZZ, PXY, PXZ, PYZ packed
into the first six words of a node and representing the moments and
products of the intertia tensor of a polyhedron of uniform (unit)
density associated with the given body. The inertia routine takes the
liberty of updating the origin of the bodies coordinates to
correspond to the center of mass and to orient the K unit vector of
the body parallel to the principal axis.
<Spatial Simulation>. The grand Euclidean space routines performing
occultation and intersection are explicated in chapters four and five
respectively. The petite space routines, listed in box 3.6, perform
propinquity, collision detection and spatial compare.{|;λ10;JAFA}
BOX 3.6 {JC} SPACE ROUTINES {I∂15,0;T200,400,600,800;}
HEXAHEDRON ← MKBUCK(BODY);
V-PIERCE ← COMPFE(FACE,EDGE);
FLAG ← COMPEE(EDGE,EDGE);
FLAG ← WITH2D(FACE,VERTEX);
FLAG ← WITH3D(BODY,VERTEX);
FLAG ← COLDET(B1,B2,EPSILON).
{|;λ30;T-1;JUFA}
\The MKBUCK routine returns a hexahedron that buckets the given body.
The COMPFE compares a face and an edge in 3-D for intersection, if
the arguments aredisjoint then zero is returned, if the arguments
intersect then the edge is split and the new vertex is position at
the locus where the edge pierces the face. The COMPEE determines
whether two edges cross in a given persepctive view. The within 2-D
routine, WITH2D, determines whether a vertex appears to be interior
to a given face in a perspective view and the WITH3D determines
whether a given vertex falls interior to a body in 3-D. Tee last
space routine compares all the vertices and faces of two objects for
propinquity within an epsilson as well as all the edges of the two
objects. Temporary collision pointers are left between vertices and
the nearest alein collision face as well as between temporary
collision vertices formed when two edges fall within an epsilon and
are split.
⊂3.4 Image Synthesis: Perspective Projection and Clipping.⊃
Image synthesis is the process of generating various kinds of
images: vector display, video, contour map or mosaic. Independent of
the final image representation the process always requires the
Euclidean operations of perspective projection and clipping. The
perspective projection takes the 3-D world locus of every potentially
visible vertex and computes a 3-D camera center coordinate locus
followed by a perspective projection in the fashion illustrated in
the PROJECT procedure given below.{λ10;W100;JAF3;}
INTEGER PROCEDURE PROJECT (INTEGER V,CAMERA);
BEGIN "PROJECT"
INTEGER TRM; REAL X,Y,Z,XCC,YCC,ZCC;
COMMENT TRANSFORM FROM WORLD COORDINATES TO CAMERA COORDIATES;
TRM ← TRAM(CAMERA);
X ← XWC(V) - XWC(TRM);
Y ← YWC(V) - YWC(TRM);
Z ← ZWC(V) - ZWC(TRM);
XCC ← X*IX(TRM) + Y*IY(TRM) + Z*IZ(TRM);
YCC ← X*JX(TRM) + Y*JY(TRM) + Z*JZ(TRM);
ZCC ← X*KX(TRM) + Y*KY(TRM) + Z*KZ(TRM);
COMMENT PERSPECTIVE PROJECTION TRANSFORMATION;
COMMENT NOTA BENE: ZPP(V) is positive when vertex is in view of camera ! ;
XPP(V) ← SCALEX(CAMERA)*XCC/ZCC; COMMENT ( SCALEX = -FOCAL/PDX );
YPP(V) ← SCALEY(CAMERA)*YCC/ZCC; COMMENT ( SCALEY = -FOCAL/PDY );
ZPP(V) ← SCALEZ(CAMERA) /ZCC; COMMENT ( SCALEZ = -FOCAL/PDZ );
RETURN (V);
END "PROJECT";{W0;}
{λ30;JUFA}\The perspective projection transformation is a 3-D
to 3-D mapping; the third component, ZPP, allows the hidden line
eliminator to perform orthographic depth comparisons. The
perspective projection is quite literally taking the whole world
model and crushing it into a slanty space between the camera lens
center and the camera focal plane. The camera scales are defined in
terms of the ficticious 3-D pixel dimensions PDX, PDY, PDZ and the
physical camera focal plane distance, FOCAL. The pixel dimensions are
arbitrarily defined as PDY=PDZ=40 microns and PDX=AR*PDY where AR is
the aspect ratio of the camera; the aspect ratio can be directly
measured by taking the ratio of the width to height of the image of a
large black sphere on a white background, AR is usually almost one.
The focal plane distance is typically between 10 and 50 millimeters
and is derived by definition from the focal ratio, FR, which can be
measured as explained in chapter nine.
The term clipping refers to the process of computing which
parts of the world model are in view of the camera. In GEOMED there
are several clipper routines: one for fast transparent refresh, three
for hidden line elimination and one more for clipping the contents of
2-D display windows that may be scrolled about. Three dimensional
clipping can be factored into a Z-clipper and an XY-clipper. The
Z-clip determines which portions of the model are in the visible 3-D
halfspace; this is finally done by similar triangles to find compute
where an edge pierces the image plane which separates the visible
halfspace from the halfspce that is out of sight. The XY-clip
determines which portion of a 2-D perspective edge is within a given
2-D rectangular window (with sides parallel to the coordiate axes).
The XY-clip is done by first applying an easy outsider test:
endpoints of edge both below, above, left or right of window;
followed by an easy insider test: endpoints of edge both inside the
window; followed by the evaluation of four polynomials of the form
A*X+B*Y+C where A,B,C are the edge coefficents and X,Y are the locus
of corners of the clip window. If all four polynomials have the same
sign the edge is a hard outsider, otherwise the intersection of a
side of the window and the edge can be detected from alternating
signs and the locus of intersect can be computed from the edge
coefficients.
⊂3.5 Image Analysis: Interface to CRE.⊃
Although there are no actual honest image analysis routines
currently implemented in GEOMED, the internal GEOMED environment was
designed for image based model synthesis and model verification. The
routine INCRE(FILENAME) inputs from DSK file a CRE node structure
that consists of a film of contour images, contour images consist of
levels, levels consist of polygons and polygons consist of vectors.
In GEOMED, the CRE polygons become two-face lamina bodies; the
contour levels hierarcy becomes parts tree structure; and a new kind
of GEOMED node called an image is introduced.
The root of the GEOMED data structure is a universe node,
which is the head of a ring of world nodes. World nodes have a ring
of body nodes and a ring of camera nodes each camera represents a
physical camera so that there might be at most three or four camera
nodes. Each camera has two rings of images: a ring of perceived
images and corresponding simulated images. The perceived image ring
is created by INCRE and the simulated image ring is created by the
hidden line eliminator, thus providing a environment for the
development of polygon based image analysis.